package NiuKe.JianZhiOffer;

public class JZ16 {
    public static void main(String[] args) {
        JZ16 jz = new JZ16();

        ListNode listNode1 = new ListNode(5);
        listNode1.next = new ListNode(8);
        listNode1.next.next =new ListNode(10);

        ListNode listNode2 = new ListNode(2);
        listNode2.next = new ListNode(3);
        listNode2.next.next =new ListNode(4);

        ListNode listNode = jz.Merge(listNode1,listNode2);

        while(true){
            if(listNode == null)break;
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }
    public ListNode Merge(ListNode list1,ListNode list2) {

        if(list1 == null){
            if(list2 == null){
                return null;
            }else{
                return list2;
            }
        }else{
            if(list2 ==null){
                return list1;
            }
        }

        ListNode newNode = null;

        if(list1.val < list2.val){
            newNode = list1;
            list1 = list1.next;
        }else{
            newNode = list2;
            list2 = list2.next;
        }

        newNode.next = null;
        ListNode head = newNode;

        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                head.next = list1;
                head = head.next;
                list1 = list1.next;
            }else{
                head.next = list2;
                head = head.next;
                list2 = list2.next;
            }
        }

        if(list1 != null){
            head.next = list1;
        }

        if(list2 != null){
            head.next = list2;
        }

        return  newNode;

    }

}
